structure GenKillgraph :
    sig

datatype gkgraph = GKGRAPH of {control: Graph.graph, gen: Graph.node list  Graph.Table.table, kill: Graph.node list Graph.Table.table, def: Graph.node list Temp.Table.table, nodestm : int Graph.Table.table, use : Graph.node list Temp.Table.table  }

	val stms2graph : Tree.stm list ->  gkgraph * Graph.node list
	val show : TextIO.outstream -> (Flow.flowgraph * Graph.node list) -> unit
    end =

struct

  structure E = ErrorMsg
  structure G = Graph
  structure GB = Graph.Table
  structure R = Tree
  structure M = Temp
  structure O = Option
  structure S = Symbol
  structure U = UnparseAbsyn
  structure W = Flow
  structure Z = Int
  datatype gkgraph= GKGRAPH of {control: G.graph, gen: G.node list GB.table, kill: G.node list GB.table, def: G.node list M.Table.table, nodestm: int GB.table , use : G.node list  M.Table.table}

		
  fun stms2graph stms = let     val control = G.newGraph ()
				val gen = ref GB.empty
				val kill = ref GB.empty
				val defs = ref M.Table.empty
				val ismove = ref GB.empty
			        val use = ref M.Table.empty
			        val nodestm = ref GB.empty
			        val j = ref 0
			    in let val nodes = map (fn i => let val node= G.newNode control in (nodestm:= GB.enter (!nodestm,node,!j); j := !j + 1 ; node) end) 
                                                     stms
			       in ( let val nextnodes = case nodes
							 of []      => []
							  | (_::ns) => ((map (fn n => SOME n) ns)@[NONE])
					fun app3 f []      []      []      = ()
					  | app3 f (x::xs) (y::ys) (z::zs) = ( f (x, y, z)
									     ; app3 f xs ys zs
									     )
					  | app3 _ _       _       _       = E.impossible "FLOWGRAPH: |INSTRS| <> |NODES| <> |NEXTNODES|"
					fun findLabeledNodes [] _                          _       = []
					  | findLabeledNodes _  []                         []      = []
					  | findLabeledNodes _  []                         _       = E.impossible "FLOWGRAPH: LESS INSTRUCTIONS THAN NODES"
					  | findLabeledNodes _  _                          []      = E.impossible "FLOWGRAPH: MORE INSTRUCTIONS THAN NODES"
					  | findLabeledNodes ls ((R.LABEL lab)::is) (n::ns) = let val ns' = findLabeledNodes ls is ns
												       in if List.exists (fn l => S.unique(l)=S.unique(lab)) ls
													  then n::ns'
													  else ns'
												       end
					  | findLabeledNodes ls (_                   ::is) (_::ns) = findLabeledNodes ls is ns
				    in let fun processInstr (R.CJUMP (rop, e1,e2,l1,l2), n, _) = 
					       ( 
					       let val labs = l1::l2::nil
								      in 
					         ( app (fn n' => G.mk_edge {from=n, to=n'})
						 (findLabeledNodes labs stms nodes))
						   end ;
							case e1 of 
							    R.TEMP t1 => case M.Table.look (!use ,t1) of SOME nodelist =>  
													      use := M.Table.enter (!use, t1, n::nodelist) ;
							case e2 of 
							    R.TEMP t2 => case M.Table.look (!use ,t2) of SOME nodelist =>  
													      use := M.Table.enter (!use, t2, n::nodelist)
					       )				
					    
														     
					     | processInstr (R.JUMP  (e, ls), n, _ ) = (( app (fn n' => G.mk_edge {from=n, to=n'})
															    (findLabeledNodes ls stms nodes));
														    
											 case e of 
							                                  R.TEMP t1 => 
											  case M.Table.look (!use ,t1) of SOME nodelist =>  
													      use := M.Table.enter (!use, t1, n::nodelist)
										       )
					     | processInstr (R.MOVE (R.TEMP t1,e2), n, SOME n') = 
					       ( G.mk_edge {from=n, to=n'};
					       		 (case M.Table.look (!defs,t1)
							   of NONE => (defs:= M.Table.enter (!defs, t1,[n]))
							    | SOME nodelist => (kill:= GB.enter (!kill, n, nodelist);						      
								 let val nodelist2 = n::nodelist
								 in 
								     defs := M.Table.enter (!defs,t1, nodelist2)
                                                                 end )
							 );
						           
							  ( 
							       case e2 of 
							        R.TEMP t => (case M.Table.look (!use ,t) of SOME nodelist => use := M.Table.enter (!use, t, n::nodelist))
							      | R.MEM (R.TEMP t) => (case M.Table.look (!use ,t) of SOME nodelist => use := M.Table.enter (!use, t, n::nodelist))
							      | R.BINOP (opr,e1, e3) => ( case e1 of R.TEMP t =>  (case M.Table.look (!use ,t) of SOME nodelist => 
                                                                                                                   use := M.Table.enter (!use, t, n::nodelist));
										          case e3 of R.TEMP t =>  (case M.Table.look (!use ,t) of SOME nodelist => 
                                                                                                                   use := M.Table.enter (!use, t, n::nodelist))
										        )
							  );
						           use := M.Table.enter (!use , t1, [n]); 
							   gen := GB.enter (!gen, n, n::nil)
					       )

 | processInstr (R.MOVE (R.TEMP t1,e2),n, NONE)    =
      ( (case M.Table.look (!defs,t1)
	   of NONE=>( defs:= M.Table.enter (!defs, t1,[n]))
	    | SOME nodelist => (kill:= GB.enter (!kill, n, nodelist);
				 let val nodelist2 = n::nodelist
                                 in defs := M.Table.enter (!defs,t1, nodelist2)
                                end)
      );   
                                                           ( 
							       case e2 of 
							        R.TEMP t => (case M.Table.look (!use ,t) of SOME nodelist => use := M.Table.enter (!use, t, n::nodelist))
							      | R.MEM (R.TEMP t) => (case M.Table.look (!use ,t) of SOME nodelist => use := M.Table.enter (!use, t, n::nodelist))
							      | R.BINOP (opr,e1, e3) => ( case e1 of R.TEMP t =>  (case M.Table.look (!use ,t) of SOME nodelist => 
                                                                                                                   use := M.Table.enter (!use, t, n::nodelist));
										          case e3 of R.TEMP t =>  (case M.Table.look (!use ,t) of SOME nodelist => 
                                                                                                                   use := M.Table.enter (!use, t, n::nodelist))
										        )
							  );
      gen := GB.enter (!gen, n, n::nil)	 )
					     | processInstr (R.LABEL lab, n, SOME n') = G.mk_edge {from=n, to=n'}
					     | processInstr (R.LABEL lab, n, NONE)    = ()
				       in ( app3 processInstr
						stms
						 nodes
						 nextnodes
					  ; (GKGRAPH { control = control
						      , def = !defs
						      , kill = !kill
						      , gen = !gen
						      , nodestm = !nodestm
						      , use = !use},
					     nodes)
					  )
				       end
				    end
				  )
			       end
			    end

  fun show stream (W.FGRAPH {control, def, use, ismove}, nodes) =
      let val _ = TextIO.print ("Nodecount: " ^ Z.toString (length nodes) ^ "\n")
	  val (_, nodeNumberTable) = foldl (fn (n, (i, nt)) => (i+1,
								GB.enter (nt, n, i)))
					   (0, GB.empty)
					   nodes
	  fun nodeName n = "(" ^ Z.toString (O.getOpt (GB.look (nodeNumberTable, n), ~1)) ^ ")"
	  fun tempNames (tab, n) = map M.makestring (O.getOpt (GB.look (tab, n), []))
      in app (fn n => ( TextIO.output (stream, (nodeName n)
					       ^ " ---> "
					       ^ (U.commaSep (map nodeName (G.succ n)))
					       ^ " DEFS: "
					       ^ (U.commaSep (tempNames (def, n)))
					       ^ "    USES: "
					       ^ (U.commaSep (tempNames (use, n)))
					       ^ "\n")
		      ; TextIO.flushOut stream
		      ))
	     nodes
      end
end
